This invention relates to two-dimensional image coding and, more particularly, to data compression in connection with vertical mode type image coding of image data representing screened images. Specifically, the invention is directed to a method and apparatus for scan line reference selection relative to coding images to enable increased data compression, for example, in connection with facsimile transmission.
Equipment for telecommunication of images is known. The images can comprise text, as well as pictorial information, such as illustrations, photographs, and graphic information. Known telecommunication equipment comprises a system whereby a transmitter at one location encodes an image, the encoded image is communicated over a communication link, such as a telephone line, to a receiver at another location, and the receiver decodes the image. The image decoded by the receiver corresponds to the image encoded by the transmitter. Consequently, a facsimile of the original image is communicated over a distance from the transmitter to the receiver. Hence, the telecommunication equipment has become known as facsimile transmission equipment.
Facsimile transmission equipment is commercially available from various manufacturers. In order to provide compatibility among the known facsimile transmission equipment produced by different manufacturers, various standards have been adopted. Typically, known facsimile transmission equipment utilizes a raster scan of an image to be coded. Known facsimile transmission equipment is also typically standardized for providing Modified Modified Read (MMR) coding, as described in "STANDARDIZATION OF GROUP 3 FACSIMILE APPARATUS FOR DOCUMENT TRANSMISSION," CCITT Recommendation T.4 (Geneva, 1980). Modified Modified Read coding includes horizontal mode coding, and the "Read" portion of "Modified Modified Read" represents relative address coding (RAC) also known as vertical mode coding.
On the one hand, the horizontal mode coding technique does not require a reference scan line in connection with coding each scanned line of the image. On the other hand, the vertical mode coding technique requires a reference scan line for each scanned line of the image as the image data is encoded for transmission at the transmitter. The reference scan line is also required by the vertical mode coding technique when the transmitted image data is decoded at the receiver.
Whether or not the horizontal or vertical mode coding technique is utilized is defined by the known CCITT facsimile coding algorithms described in the aforementioned CCITT Recommendation T.4 entitled "STANDARDIZATION OF GROUP 3 FACSIMILE APPARATUS FOR DOCUMENT TRANSMISSION" (Geneva, 1980). These standards specify conditions under which the vertical mode coding technique may be utilized. If both the reference scan line and the current scan line are used for coding, the process is referred to as vertical mode coding. If the current scan line alone is used for coding, the process is referred to as horizontal mode coding.
Typically, the major cost for operation of known facsimile transmission equipment is the cost of the communication link, such as a telephone line. Preferably, the image data is compressed by means of the known CCITT facsimile data compression coding algorithms utilizing the vertical mode coding technique prior to facsimile transmission. The purpose of the data compression is to reduce the amount, more particularly, the number of bits, of image data to be transmitted, thereby reducing the operating cost. Presently, the amount of image data to be transmitted is of particular concern in the case of pictorial information.
Known facsimile transmission equipment generally requires that a pictorial image be screened prior to coding and transmitting the image. Screening a pictorial image can be performed in several ways.
Screened pictorial images under a magnifying glass generally comprise either circular or diamond-shaped dots aligned in vertical columns. The size of each circle or diamond, or the density of circles or diamonds, in a given area of the pictorial image varies as a function of the gray scale for the given area.
Unfortunately, if a screened pictorial image is to be transmitted, the CCITT facsimile data compression coding algorithms do not operate well, because these algorithms cannot optimally utilize the typical Delta Modulation scheme which is employed whereby the current scan line to be coded is represented by coding only the changes or differences between the current scan line and the reference scan line and the result or difference data comprises the image data which is communicated. Invariably, the CCITT facsimile data compression coding algorithms utilize the Delta Modulation scheme for compressing the current scan line to be coded based on the immediately preceding scan line. The immediately preceding scan line is used as a reference scan line so that the current scan line to be coded can be represented by coding only the changes or differences between the current scan line to be coded and the immediately preceding scan line. However, the differences between the current scan line to be coded and the immediately preceding scan line can be great. Consequently, the amount of image data transmitted over the communication link can be substantial. This translates to a high cost for operation of the facsimile transmission equipment, since the cost for the use of the communication link is based on the amount of image data which is communicated.